#include <iostream>
#include <vector>
using namespace std;

class dpStone {
public:
    bool stoneGame(vector<int>& piles) {
        int n = piles.size();
        pair<int, int> dp[n][n];

        // dp[i][j]: (i...j)区间内：first(先手石头最多数目)，second(后手石头最多数目)
        // base case
        for (int i = 0; i < n; i++) {
            dp[i][i].first = piles[i];
            dp[i][i].second = 0;
        }

        // 斜着遍历dpTable
        for (int step = 1; step < n; step++) {
            for (int i = 0; i < n - step; i++) {
                int j = step + i;
                // 先手选左边或右边
                int left = piles[i] + dp[i + 1][j].second;
                int right = piles[j] + dp[i][j - 1].first;
                // 状态转移
                if (left > right) {
                    dp[i][j].first = left;
                    dp[i][j].second = dp[i + 1][j].first;
                }
                else {
                    dp[i][j].first = right;
                    dp[i][j].second = dp[i][j - 1].first;
                }
            }
        }

        return dp[0][n - 1].first > dp[0][n - 1].second;
    }
};

class dpStone2 {
public:
    bool stoneGame(vector<int>& piles) {
        // dp[i][j]: (i...j)区间，先手石头数与后手石头数的最大差值
        int n = piles.size();
        vector<vector<int> > dp(n, vector<int>(n));
        for (int i = 0; i < n; i++)
            dp[i][i] = piles[i];

        for (int i = n - 2; i >= 0; i--)
            for (int j = i + 1; j < n; j++)
                // piles[i] - dp[i + 1][j] = piles[i] - (前一层先手减去后手) = 前一层后手 + 这一层先手 - 前一层先手
                dp[i][j] = max(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1]);

        return dp[0][n - 1] > 0;
    }

    bool stoneGameSpace(vector<int>& piles) {
        // dp[i][j]: (i...j)区间，先手石头数与后手石头数的最大差值
        // 将dp[i][j]二维数组压缩到dp[j]的一维数组，就是将dpTable沿x轴压扁，然后从左往右遍历即可得到所有结果
        int n = piles.size();
        vector<int> dp(n);
        for (int i = 0; i < n; i++)
            dp[i] = piles[i];

        for (int i = n - 2; i >= 0; i--)
            for (int j = i + 1; j < n; j++)
                // piles[i] - dp[i + 1][j] = piles[i] - (前一层先手减去后手) = 前一层后手 + 这一层先手 - 前一层先手
                dp[j] = max(piles[i] - dp[j], piles[j] - dp[j - 1]);

        return dp[n - 1] > 0;
    }
};